def extend_shortest_paths(L, W):
    for i in xrange(1, n + 1):
        for j in xrange(1, n + 1):
            for k in xrange(1, n + 1):
                L[i,j] = min(L[i,j], L[i,k] + W[k,j])

def slow_all_shortest_paths(W):
    L = copy.copy(W)
    for m in xrange(n - 2):
        extend_shortest_paths(L, W)
    return L

def faster_all_shortest_paths(W):
    L = copy.copy(W)
    m = 1
    while m < n - 1:
        extend_shortest_paths(L, L)
        m = 2 * m
    return L

def prt_L(L):
    for i in xrange(1, n + 1):
        for j in xrange(1, n + 1):
            print '%2d' % L[i,j],
        print

if __name__ == '__main__':
    import copy
    from collections import defaultdict
    es = [(1,2,3), (1,3,8), (1,5,-4),
          (2,4,1), (2,5,7),
          (3,2,4),
          (4,1,2), (4,3,-5),
          (5,4,6)]
    n = 5
    inf = 2**100
    W = defaultdict(lambda: inf)
    for i in xrange(1, n + 1):
        W[i, i] = 0
    for (u, v, w) in es:
        W[u, v] = w
    L = slow_all_shortest_paths(W)
    print 'L: (by slow_all_shortest_paths)'
    prt_L(L)
    L = faster_all_shortest_paths(W)
    print 'L: (by faster_all_shortest_paths)'
    prt_L(L)
